// @algorithm @lc id=912 lang=cpp 
// @title random-pick-with-weight
class Solution {
    // std::random_device;  //Will be used to obtain a seed for the random number engine
    std::mt19937 gen; //Standard mersenne_twister_engine seeded with rd()
    std::uniform_int_distribution<> distrib;
    vector<int> preSum;
public:
    Solution(vector<int>& w)
    : gen( std::random_device{}() )
    , distrib(1, accumulate(w.begin(), w.end(), 0))
    , preSum(w.size(), 0)
    {
        partial_sum(w.begin(), w.end(), preSum.begin());
    }
    
    int pickIndex() {
        int randomValue = distrib(gen);
        return lower_bound(preSum.begin(), preSum.end(), randomValue) - preSum.begin();
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(w);
 * int param_1 = obj->pickIndex();
 */